import java.util.Random;


public class TestBank {

    static class Account {
        private int balance;

        public Account(int initial) {
            this.balance = initial;
        }
        
        // uncomment the synchronized to make this class thread-safe
        //synchronized 
        public void deposit(int amount) {
            this.balance = this.balance + amount;
        }

        public void withdraw(int amount) {
            deposit(-amount);
        }

        public int getBalance() {
            return balance;
        }
    }


    static class Bank {
        static final int NUM_ACCS = 1000;

        Account[] accounts = new Account[NUM_ACCS];
        
        public Bank() {
            for (int i = 0; i < accounts.length; i++) {
                accounts[i] = new Account(100);
            }
        }

        public Account getAccount(int num) {
            return accounts[num];
        }
        
        public void transfer(int from, int to, int amount) {
            accounts[from].withdraw(amount);
            accounts[to].deposit(amount);
        }

        // this version of the transfer operation is atomic (with
        // respect to other operations that follow the same locking
        // protocol)
        public void atomicTransfer(int from, int to, int amount) {
            Account ac1 = accounts[from];
            Account ac2 = accounts[to];

            Account ac1ToLock = from < to ? ac1 : ac2;
            Account ac2ToLock = from < to ? ac2 : ac1;

            synchronized (ac1ToLock) {
                synchronized (ac2ToLock) {
                    ac1.withdraw(amount);
                    ac2.deposit(amount);
                }
            }
        }


        // non-atomic version of getBankBalance
        public int getBankBalance() {
            int total = 0;
            for (Account ac : accounts) {
                total += ac.getBalance();
            }
            return total;
        }

        // atomic version of getBankBalance
        public int atomicGetBankBalance() {
            return lockAndSum(0);
        }

        private int lockAndSum(int i) {
            if (i >= accounts.length) {
                return 0;
            } else {
                synchronized (accounts[i]) {
                    return accounts[i].getBalance() + lockAndSum(i + 1);
                }
            }
        }
    }


    private static final Bank bank = new Bank();

    private static void reportTotalOfBank() {
        // comment/uncomment to use the atomic or non-atomic version
        //System.out.println("Bank total = " + bank.getBankBalance());
        System.out.println("Bank total = " + bank.atomicGetBankBalance());
    }

    public static void main(String[] args) throws Exception {
        reportTotalOfBank();

        Thread[] ts = new Thread[100];

        for (int i = 0; i < ts.length; i++) {
            //ts[i] = new DepositThread();
            ts[i] = new TransferThread();
        }

        Thread rt = new ReportThread();
        rt.setDaemon(true);
        rt.start();

        long start = System.nanoTime();
        for (Thread t : ts) {
            t.start();
        }

        for (Thread t : ts) {
            t.join();
        }

        long time = System.nanoTime() - start;
        reportTotalOfBank();
        System.out.println(time/1e6);
    }

    static final Random RNG = new Random();

    static final ThreadLocal<Random> threadRNG = new ThreadLocal<Random>() {
        public Random initialValue() {
            return new Random();
        }
    };

    private static int randomInt(int max) {
        // use a shared Random among all threads
        return RNG.nextInt(max);

        // use a per-thread Random object
        //return threadRNG.get().nextInt(max);
    }


    static class DepositThread extends Thread {
        public void run() {
            int amount = 10;
            for (int i = 0; i < 10*1000; i++) {
                int index = randomInt(Bank.NUM_ACCS);
                bank.getAccount(index).deposit(amount);
                amount *= -1;
            }
        }
    }


    static class TransferThread extends Thread {
        public void run() {
            int amount = 10;
            for (int i = 0; i < 10*1000; i++) {
                int index1 = randomInt(Bank.NUM_ACCS);
                int index2 = randomInt(Bank.NUM_ACCS);

                //bank.transfer(index1, index2, amount);
                bank.atomicTransfer(index1, index2, amount);

                // use inlined version of transfer to break locking scheme
                //bank.getAccount(index1).withdraw(amount);
                //bank.getAccount(index2).deposit(amount);
                
                amount *= -1;
            }
        }
    }


    static class ReportThread extends Thread {
        public void run() {
            while (true) {
                reportTotalOfBank();
                try {
                    Thread.sleep(10);
                } catch (InterruptedException ie) {
                    // ignore
                }
            }
        }
    }
}
